import java.util.ArrayList;


/**
 * This class is the algorithm class, call the minimax algorithm
 * @author minh-tuan
 *
 */
public class AlgorithmThread extends Thread {
	//reference to the parent class to get the reference
	GameRunThread grt;
	
	//get the signal from the game run thread to stop
	public boolean stop;
	
	//when the algorithm is done
	boolean done = false;
	
	//highest level reached
	int hLevel = 0;
	
	public AlgorithmThread(GameRunThread grt)
	{
		this.grt = grt;
		stop = false;
	}
	
	@Override
	public void run()
	{
		//max level of each run
		int depth = 1;
		//copy the board
		Board board = new Board(grt.gs.game.board);
		
		hLevel = 0;
		done = false;
		stop = false;
		
		//run while not signaled to stop and not done yet
		while (!stop && !done)
		{
			Move t = maximize(board, depth, 0, 0, 0, Integer.MIN_VALUE, Integer.MAX_VALUE, true);
			
			if (stop == false)
				grt.curMove = t;
			
			//done
			if (hLevel < depth)
			{
				done = true;
			}
			
			depth++;
		}
		
		if (done)
			grt.interrupt();
	}
	
	public Move maximize(Board b, int d, int curLev, int pfdot, int psdot, int alpha, int beta, boolean isMaximized)
	{
		//if reached the desired level
		if (curLev == d || b.winner() != 0)
		{
			if (hLevel < curLev)
				hLevel = curLev;
			
			//if the method calls this method is maximized method, means the computer made the move
			int v;
			if (isMaximized)
				v = b.evaluate('C');
			else //if not maximize, means minimize called, means the last call was caused by the player
				v = b.evaluate('P');
			return new Move(pfdot, psdot, v);
		}
		
		//move v of -inf
		Move mv = new Move(0, 0, Integer.MIN_VALUE);
		
		//get available moves
		ArrayList<Move> moves = b.getAvailableMoves();
		
		for (int i = 0; i < moves.size(); i++)
		{
			//move
			int result = b.move(moves.get(i).fDot, moves.get(i).sDot, 'C');
			Move maxMove = new Move(0, 0, 0);

			//if doesn't win the square, change turn normally
			if (result == 0)
			{
				maxMove = minimize(b, d, curLev + 1, moves.get(i).fDot, moves.get(i).sDot, alpha, beta, true);
			}
			else if (result == 1) //won the square
			{
				maxMove = maximize(b, d, curLev + 1, moves.get(i).fDot, moves.get(i).sDot, alpha, beta, true);
			}

			//redo the move
			b.redo(moves.get(i).fDot, moves.get(i).sDot, 'C');
			
			if (mv.v < maxMove.v)
			{
				mv.v = maxMove.v;
				mv.fDot = moves.get(i).fDot;
				mv.sDot = moves.get(i).sDot;
			}
			
			//if v >= beta, return v
			if (mv.v >= beta)
			{
				return mv;
			}
			
			if (mv.v > alpha)
			{
				alpha = mv.v;
			}
		}
		
		return mv;
	}
	
	public Move minimize(Board b, int d, int curLev, int pfdot, int psdot, int alpha, int beta, boolean isMaximized)
	{
		//if reached the desired level
		if (curLev == d || b.winner() != 0)
		{
			if (hLevel < curLev)
				hLevel = curLev;
			
			//if the method calls this method is maximized method, that means we have 2 turns in a row
			int v;
			if (isMaximized)
				v = b.evaluate('C');
			else //if not maximize, means minimize called, means the last call was caused by the player
				v = b.evaluate('P');
			return new Move(pfdot, psdot, v);
		}
		
		//move v of +inf
		Move mv = new Move(0, 0, Integer.MAX_VALUE);

		//get available moves
		ArrayList<Move> moves = b.getAvailableMoves();

		for (int i = 0; i < moves.size(); i++)
		{
			//move
			int result = b.move(moves.get(i).fDot, moves.get(i).sDot, 'P');
			Move minMove = new Move(0, 0, 0);

			//if doesn't win the square, change turn normally
			if (result == 0)
			{
				minMove = maximize(b, d, curLev + 1, moves.get(i).fDot, moves.get(i).sDot, alpha, beta, false);
			}
			else if (result == 1) //won the square
			{
				minMove = minimize(b, d, curLev + 1, moves.get(i).fDot, moves.get(i).sDot, alpha, beta, false);
			}

			//redo the move
			b.redo(moves.get(i).fDot, moves.get(i).sDot, 'P');

			if (mv.v > minMove.v)
			{
				mv.v = minMove.v;
				mv.fDot = moves.get(i).fDot;
				mv.sDot = moves.get(i).sDot;
			}

			//if v >= beta, return v
			if (mv.v <= alpha)
			{
				return mv;
			}
			
			if (mv.v < beta)
			{
				beta = mv.v;
			}
		}
		
		return mv;
	}
}
